#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        cout << "nums:" << endl;
        print(nums);
        mergeSort(nums,0,nums.size()-1);
        cout << "sort:" << endl;
        print(nums);
        return nums;
    }

    //归并排序
    void mergeSort(vector<int>& nums, int lo, int hi) {
        if(lo >= hi) {
            return;
        }
        int mid = lo - (lo - hi) / 2;
        // int mid = (lo + hi) / 2;
        cout << "lo:" << lo << " hi:" << hi  << " mid:" << mid << endl;
         //排序
        mergeSort(nums,lo,mid);
        mergeSort(nums,mid+1,hi);
        //归并
        merge(nums,lo,hi,mid);
    }

    void merge(vector<int>& nums, int lo, int hi, int mid) {
        vector<int> tem;
        int p1 = lo;
        int p2 = mid+1;
        while(p1 <= mid && p2 <= hi) {
            if(nums[p1] <= nums[p2]) {
                tem.push_back(nums[p1++]);
            } else {
                tem.push_back(nums[p2++]);
            }
        }
        while(p1 <= mid) {
            tem.push_back(nums[p1++]);
        }
        while(p2 <= hi) {
            tem.push_back(nums[p2++]);
        } 
        for(int i = lo; i <= hi; i++) {
            nums[i] = tem[i-lo];
        }
        
    }

    //打印数组
    void print(vector<int>& nums) {
        for(auto it = nums.begin(); it != nums.end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
    }

    //测试
    void test() {
        vector<int> nums = {1,3,2,5,4};
        sortArray(nums);
    }
};

int main() {
    Solution().test();
    return 0;
}